The present invention relates to the field of error-control coding, and more specifically with error correction using binary shortened cyclic codes.
Data transmission over a channel is prone to errors due to numerous factors such as fading, channel noise and signal interference. These errors cause the receiver to obtain a corrupted form of the transmitted signal. A variety of error-control coding schemes have been proposed to perform error-detection and error-correction. The underlying principle of all of these schemes is to add redundancy to the transmitted data such that the errors during transmission may be detected and corrected. The schemes select a code-word for every message-word to be transmitted. The selected code-word represents the data of the message-word and additionally has a redundant data component, which is used for error-control. The amount of redundancy added is a function of the error-control capability of the scheme. At the receiver, a corrupted form of the transmitted code-word is received. However, if the errors in the received code-word are within the error-control capability of the scheme, the receiver can determine the correct message-word corresponding to the received code-word.
One of the most prevalent error-control coding schemes used today is the cyclic code. A (n,k) cyclic code encodes message-words of length k bits into code-words of length n bits. The basic property of a cyclic code is that the result of a cyclic shift operation performed on one code-word of the cyclic code yields another code-word of the cyclic code. Mathematically, for every code-word C=(c0, c1, . . . , cn−1), the result of a right cyclic shift operation i.e. C1=(cn−1, c0, . . . , cn−2) is also a code-word. These code-words are obtained from the message-words using a generator g(x) associated with the cyclic code. The generator of degree n−k uniquely defines the cyclic code and is mathematically represented as:g(x)=1+g1x+g2x2+ . . . +gn−k−1xn−k−1+xn−k 
where, g1 to gn−k−1 are referred to as the coefficients of the generator.
The encoding and the decoding operations of a cyclic code can be achieved through the use of Linear Feedback Shift Registers (LFSRs). The encoding process using cyclic codes produces an n bit code-word containing the k bit message-word and n−k additional parity bits. The parity bits are computed using an LFSR that has its feedback connections weighted by the coefficients of the generator of the cyclic code. The k bits of the message-word are sequentially fed into the LFSR. Once the whole message-word has been fed into the LFSR, the contents of the LFSR define the parity bits. The n bit code-word thus produced contains k bits of the message-word followed by n−k parity bits. An implementation of an encoder for cyclic codes using an LFSR is described in the 4th edition of “Communication Systems” by Simon Haykin, published by John Wiley and Sons, Inc.
The decoding of the corrupted code-word to remove a burst error pattern involves the following steps. First, an n−k bit syndrome corresponding to the corrupted code-word is calculated. The syndrome is characteristic of the burst error pattern present in the corrupted code-word. The importance of the syndrome lies in the fact that it depends only on the burst error pattern, and not on the code-word itself. Hence, the syndrome is subsequently used to identify the burst error pattern present in the corrupted code-word through a process known as error-trapping. The error-trapping algorithms assume that a burst error is present in the corrupted code-word. A burst error of at most b bits is correctable by the cyclic code, where b is the error-control capability of the cyclic code. Once the b bit error pattern is identified, a corresponding correction is applied to the corrupted code-word to correct the error and obtain the original transmitted code-word.
An advantage of cyclic codes is that their encoding process is simple. Further, cyclic codes possess a well-defined mathematical structure, which has led to the development of very efficient decoding schemes for them. A method for decoding of cyclic codes is described in the European Patent Office (EPO) patent application number EP 1,274,173 A2, titled “Error Trapping And Correction For Cyclic Codewords” of Matsushita Electric Industrial Co., Ltd.
However, one of the major drawbacks of cyclic codes is that it is not always possible to find a suitable cyclic code for the desired length of the message-word. A way of overcoming this is to select a cyclic code suitable for use with a message-word of length greater than the desired length of the message-word. In this case, a zero-portion is added to the message-word to increase its length to the length used by the cyclic code. However, this solution turns out to be wasteful in terms of complexity of the decoders, as well as in terms of the bandwidth used for transmission. This problem is a major concern if the size of the zero-portion is large. For instance, in the European Global System for Mobile Communications (GSM) protocol, a message-word of length 184 bits is required to be transmitted with 40 additional parity bits. However, for selection of a suitable cyclic code, a zero-portion of 3014409 bits needs to be added to this message-word.
To minimize the waste incurred due to the zero-portion, a special class of cyclic codes, called shortened cyclic codes, is used. A (n−l, k−l) shortened cyclic code encodes a message-word of length k−l bits into a code-word of length n−l bits wherein the zero-portion of the message-word is of length l bits. A shortened cyclic code does not have the properties of a cyclic code, but it uses the properties applicable to a (n,k) cyclic code for the encoding and the decoding process. GSM uses a special class of shortened cyclic codes called Fire codes. The Fire coding method used for GSM selects a code-word of length 224 bits to represent the message-word of length 184 bits and uses a zero-portion of 3014409 bits. Thus, the Fire code used in GSM is a (3014633-3014409, 3014593-3014409) shortened cyclic code. However, a major drawback of the already available shortened cyclic code decoders is the complexity of the syndrome calculation operation.
Some approaches for decoding of shortened cyclic codes have been suggested in the prior art to reduce the computational complexity of syndrome calculation. One such approach is described in the U.S. Pat. No. 5,936,978 titled “Shortened Fire Code Error-Trapping Decoding Method And Apparatus” assigned to Telefonaktiebolaget L M Ericsson, Stockholm, Sweden. However, the approach described in this patent requires the knowledge of inverse cyclic codes. Further, the approach requires considerable amount of hardware for implementation.
Thus, there is a need for a simpler approach for decoding of binary shortened cyclic codes, which requires lesser hardware for implementation.